'''这两天看了不少讲Floyd算法的文章，大概理解了其中的思想
然后自己动手，从图和节点类的定义开始，整个自己写了一下
和其他博主的实现方式上会有一些差别，注释我都写上了，有问题期待交流'''
import numpy as np
import time


# 开始创建图

class Vertex():
    def __init__(self, key):
        self.id = key  # 存储节点名称
        self.connectedTo = {}  # 存储相邻节点信息

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight  # 添加相邻节点
        # nbr.connectedTo[self] = weight #实现双向互通

    def getConnections(self):
        return self.connectedTo.keys()  # 返回所有相邻节点的信息

    def getId(self):
        return self.id  # 返回当前节点的名称

    def getWeight(self, nbr):
        if nbr not in self.connectedTo.keys() and nbr != self:
            return 99999
        elif nbr == self:
            return 0
        else:
            return self.connectedTo[nbr]  # 返回指定相邻节点的权重

    def __str__(self):
        return str(self.getId()) + 'connected to' + str([x.getId() for x in self.connectedTo.keys()])  # 打印时返回节点的连接信息


class Graph():
    def __init__(self):
        self.verList = {}  # 以字典的形式存储节点和节点对象
        self.size = 0  # 图的大小

    def addVertex(self, key):
        '''向图中添加节点'''
        self.verList[key] = Vertex(key)
        self.size += 1

    def getVertex(self, key):
        '''返回节点信息'''
        if key in self.verList.keys():
            return self.verList[key]
        else:
            return False

    def __contains__(self, key):
        return key in self.verList.keys()  # 判断节点是否在图中

    def addEdge(self, fromV, toV, cost=0, directed=False):
        '''向图中添加一条边'''
        if fromV not in self.verList.keys():
            self.addVertex(fromV)
        if toV not in self.verList.keys():
            self.addVertex(toV)

        self.verList[fromV].addNeighbor(self.verList[toV], weight=cost)
        if (directed == False):
            self.verList[toV].addNeighbor(self.verList[fromV], weight=cost)

    def getVertice(self):
        return self.verList.keys()  # 返回节点列表

    def __iter__(self):
        return iter(self.verList.values())

    def __len__(self):
        return len(self.verList.keys())


g = Graph()
for i in range(1, 7):
    g.addVertex(i)
g.addEdge(1, 2, 1)
g.addEdge(1, 6, 2)
g.addEdge(2, 3, 4)
g.addEdge(3, 6, 1)
g.addEdge(3, 4, 2)
g.addEdge(4, 6, 3)
g.addEdge(5, 6, 5)
g.addEdge(4, 5, 3)
# 先构建一个邻接矩阵来存放任意两点之间的距离
size = g.__len__()
dis = np.zeros((size, size))

for i, vertice in enumerate(g):
    temp = np.zeros((1, 6))
    for j, v in enumerate(g):
        temp[0, j] = vertice.getWeight(v)
    dis[i, :] = temp


def getFloydMatrix(dis: np.array([])):
    size = dis.shape[0]
    for k in range(size):  # 将每个点轮流设置为中转点
        for i in range(size):  # 遍历起点
            for v in range(size):  # 遍历终点
                # 如果经过中转点的距离小于原始距离
                if dis[i, v] > dis[i, k] + dis[k, v]:
                    dis[i, v] = dis[i, k] + dis[k, v]
    return dis


dis = getFloydMatrix(dis)

print(dis)
